package com.gitee.ywj1352.算法.真实;

/**
 * @author: yangwenjie.a
 * @date: 2021/5/7 09:50
 * @description:
 */
public class N个数子第K大的字典排序 {

    public static int findKthNumber(int n, int k) {
        int cur = 1;
        k = k - 1;//扣除掉第一个0节点
        while(k>0){
            //节点数量
            int num = getNode(n,cur,cur+1);
            System.out.println(num);
            //不在当前节点上
            if(num<=k){//第k个数不在以cur为根节点的树上
                cur+=1;//cur在字典序数组中从左往右移动
                //向右边移动 走出了 子节点数个步骤
                k-=num;
            }else{//在子树中
                cur *= 10;//cur在字典序数组中从上往下移动
                k-=1;//刨除根节点
            }
        }
        return cur;
    }
    //这里有个技巧 求两字典树 之间 的 节点数量
    public static int getNode(int n, long first, long last){
        int num = 0;
        while(first <= n){
            //System.out.println(Math.min(n+1,last) - first);
            num += Math.min(n+1,last) - first;//比如n是195的情况195到100有96个数
            first *= 10;
            last *= 10;
        }
        return num;
    }

    public static void main(String[] args) {
        int kthNumber = findKthNumber(2123412, 1345);
        //System.out.println(kthNumber);
    }


}
